package club.vann.nowcoder;

/**
 * <p>难度：Medium</p>
 * <p></p>
 * <p></p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-23:17:59:57
 */
public class NC29 {
    public static void main(String[] args) {
        NC29 nc29 = new NC29();

        System.out.println(nc29.searchMatrix(TestCase.MATRIX, TestCase.TARGET));
        System.out.println(nc29.searchMatrix(TestCase.MATRIX1, TestCase.TARGET1));
    }

    /**
     *
     * @param matrix int整型二维数组
     * @param target int整型
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        if(matrix == null || matrix.length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        // 从右上角开始找
        int y = 0, x = n-1;
        while(y < m && x >= 0) {
            if(matrix[y][x] == target) {
                return true;
            } else if(matrix[y][x] < target) {
                y ++;
            } else {
                x --;
            }
        }
        return false;
    }

    static class TestCase {
        public static boolean ANS = true;
        public static int[][] MATRIX = {{1, 3, 5, 9}, {10, 11, 12, 30}, {230, 300, 350, 500}};
        public static int TARGET = 3;

        public static boolean ANS1 = false;
        public static int[][] MATRIX1 = {{1, 3, 5, 9}, {10, 11, 12, 30}, {230, 300, 350, 500}};
        public static int TARGET1 = 4;
    }
}
